查找算法 二分查找
二分查找是什么？
在计算机科学中，二分搜索（binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
二分查找的时间复杂度是 （注意，不写底数就是默认以 2 为底），因为二分查找是每次都折半的，所以很明显是 logn 的时间复杂度
非递归方式代码实现
采用非递归方式完成二分查找法。Java 代码如下所示。
public class BinarySearch {
public static void main(String[] args) {
int[] array = new int[]{-7, -4, -2, 5, 8, 10};
System.out.println("原始数据：" + Arrays.toString(array));
int index = binarySearch(array, 8);
System.out.println("【非递归方式二分查找】结果下标位置：" + index);
}
/**
* 二分查找
*/
public static int binarySearch(int[] array, int value) {
int mid;
int start = 0;
int end = array.length - 1;
while (start <= end) {
mid = (end - start) / 2 + start;
// 说明在左边
if (value < array[mid]) {
end = mid - 1;
}
// 说明在右边
else if (value > array[mid]){
start = mid + 1;
} else {
return mid;
}
}
return -1;
}
}
递归方式代码实现
采用递归方式完成二分查找算法。代码如下所示。
/**
* @author alsritter
* @version 1.0
**/
public class BinarySearch {
public static void main(String[] args) {
int[] array = new int[]{-7, -4, -2, 5, 8, 10};
System.out.println("原始数据：" + Arrays.toString(array));
int index = binarySearch(array, 8, 0, array.length - 1);
System.out.println("【递归方式二分查找】结果下标位置：" + index);
}
/**
* 递归的二分查找
*/
public static int binarySearch(int[] array, int value, int start, int end) {
int mid = (end - start) / 2 + start;
if (array[mid] == value) return mid;
if (start >= end) {
return -1;
}
// 说明在左边
else if (value < array[mid]) {
return binarySearch(array, value, start, mid - 1);
}
// 说明在右边
else if (value > array[mid]) {
return binarySearch(array, value, mid + 1, end);
}
return -1;
}
}
有序数组查找多个结果
当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到
{1, 8, 10, 89, 1000, 1000, 1234} 如这里的 1000
思路分析：
- 在找到 mid 索引值，不要马上返回
- 向 mid 索引值的左边扫描，将所有满足 1000 的元素下标，加入到集合中（ArrayList）
- 向 mid 索引值的右边扫描，将所有满足 1000 的元素下标，加入到集合中（ArrayList）
- 将 ArrayList 返回
/**
* 二分查找顺序数组的多个结果
*/
public static List<Integer> binarySearch2(int[] array, int value) {
int mid;
int start = 0;
int end = array.length - 1;
ArrayList<Integer> result = new ArrayList<>();
while (start <= end) {
mid = (end - start) / 2 + start;
// 说明在左边
if (value < array[mid]) {
end = mid - 1;
}
// 说明在右边
else if (value > array[mid]) {
start = mid + 1;
} else {
// 到了这里表示已经找到目标值了
int temp = mid - 1;
// 先检查左边的
while (temp >= 0 && array[temp] == value) {
// 否则就 temp 放入到 result 里面
result.add(temp);
temp--; // 左移
}
// 再检查右边的
while (temp <= array.length - 1 && array[temp] == value) {
// 否则就 temp 放入到 result 里面
result.add(temp);
temp++; // 右移
}
}
}
return result;
}
链表的二分查找：跳跃表
补充一个链表的二分查找：跳跃表
局部最小问题
题目：给定一个无序数组，并且相邻两个元素不相等，返回任意一个局部最小值
局部最小值的定义为：
- 对于第一个元素而言，只要它比第二个元素要小，则就是局部最小值。
- 同理，对于最后一个元素而言，只要它比倒数第二个元素要小，则就是局部最小值。
- 对于数据中间的元素，如果一个数相邻的两个数都比他大，那么他就是局部最小值。
这里解释一下第三种情况，如果上面两种情况都不满足就是如下图这样
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] A = {19, 11, 3, 8, 10};
System.out.println(BinarySearch(A));
}
private static int BinarySearch(int[] nums) {
// 规定当数组中只有一个数时，不存在局部最小值
if (nums == null || nums.length <= 1) {
return 0;
}
int len = nums.length;
if (nums[0] < nums[1]) {
return nums[0];
}
if (nums[len - 1] < nums[len - 2]) {
return nums[len - 1];
}
int start = 0;
int end = len - 1;
// 还是可以使用二分法
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] > nums[mid + 1]) {
start = mid + 1;
} else {
end = mid;
}
}
return (nums[start] < nums[start + 1]) ? nums[start] : nums[end];
}
}